package leetcode;

import java.util.LinkedList;

public class Lc200_2 {

    int[] X = {0, 0, -1, 1};
    int[] Y = {-1, 1, 0, 0};
    public void dfs(char[][] grid, int x, int y) {

        for (int i = 0; i < 4; i++) {
            int nx = x + X[i];
            int ny = y + Y[i];
            if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length)
                continue;
            if ('1' == grid[nx][ny]) {
                grid[nx][ny] = '2';
                dfs(grid, nx, ny);
            }
        }
    }

    public int numIslands(char[][] grid) {

        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if ('1' == grid[i][j]) {
                    ans ++;
                    dfs(grid, i, j);
                }
            }
        }
        return ans;
    }



    //队列实现
    public int numIslands2(char[][] grid) {
        int ans = 0;
        LinkedList<int[]> queue = new LinkedList<>();

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    ans ++;
                    grid[i][j] = '2';
                    queue.offer(new int[]{i, j});
                    while (!queue.isEmpty()) {
                        int sz = queue.size();
                        while (sz -- > 0) {
                            int x = queue.peek()[0];
                            int y = queue.peek()[1];
                            queue.pop();
                            for (int k = 0; k < 4; k++) {
                                int nx = x + X[k];
                                int ny = y + Y[k];
                                if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length)
                                    continue;
                                if (grid[nx][ny] == '1') {
                                    queue.offer(new int[]{nx, ny});
                                    grid[nx][ny] = '2';
                                }
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }


}
